#ifndef DAG_GENERATOR_HPP_
#define DAG_GENERATOR_HPP_

/**
 * @file dag_generator.hpp
 * @brief randomly generate directed acyclic graph
 * @author Hu Qian
 * @date 2014-10.30
 * @version 0.1 create
 */

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/copy.hpp>
using namespace boost;

/*
Examples:

1. generate a random weight dag with communication cost

	dag::RandomGenerator<> rg;
	dag::RandomGenerator<>::DirectedGraph g = rg.Generate(5);
	rg.printGraph( g );


2. generate a random weight dag without communication cost

	using namespace dag;
	RandomGenerator<CostRandome100Generator,CostZeroGenerator> rgNoCommunication;
	RandomGenerator<CostRandome100Generator,CostZeroGenerator>::DirectedGraph gNoCommunication = rgNoCommunication.Generate(5);
	rgNoCommunication.printGraph( gNoCommunication );


3. list all vertices weight

	dag::RandomGenerator<> rg;
	dag::RandomGenerator<>::DirectedGraph g = rg.Generate(5);
	std::pair<dag::RandomGenerator<>::iter_t, dag::RandomGenerator<>::iter_t> p;
	for(  p = vertices(g); p.first != p.second; ++p.first ){
		cout << "Node " << *p.first << ": " << g[ *p.first ].cost << endl;
	}


4. list all edges weight

	dag::RandomGenerator<> rg;
	dag::RandomGenerator<>::DirectedGraph g = rg.Generate(5);
	std::pair<dag::RandomGenerator<>::edge_iterator, dag::RandomGenerator<>::edge_iterator> p;
	for(  p = edges(g); p.first != p.second; ++p.first ){
		cout << "Edge from Node " << source(*p.first, g)
			<< " to Node " << target(*p.first, g)
			<< " : " << get(edge_weight, g, *p.first) << endl;
	}

*/

namespace dag{

	// randomly generate integer from 0 to 99
	class CostRandom100Generator{
	public:
		int generate() const{
			return rand() % 100;
		};
	};

	// generate zero only
	class CostZeroGenerator
	{
	public:
		int generate() const{
			return 0;
		}
	};

	/************************************************************************/
	/*    class Generator                                                   */
	/*            the class generates directed acyclic graph				*/
	/************************************************************************/

	template <typename TASK_COMPUTATION_COST_GENERATOR = CostRandom100Generator, 
			  typename COMMUNICATION_COST_GENERATOR = TASK_COMPUTATION_COST_GENERATOR>
	class RandomGenerator{

	public:
		// vertex property
		struct vertex_info{
			int cost;
			int reserve;	// this can be used for custom info, for example processor id.
			vertex_info() : cost(0), reserve(0){};
		};

		typedef typename property<edge_weight_t, int> EdgeProperty;
		typedef typename adjacency_list<vecS, vecS, bidirectionalS, vertex_info, EdgeProperty> DirectedGraph;
		typedef typename graph_traits<DirectedGraph>::vertex_iterator iter_t;
		typedef typename graph_traits<DirectedGraph>::edge_iterator edge_iterator;

	protected:
		
		// task computation cost (random) generator
		const TASK_COMPUTATION_COST_GENERATOR	task_computation_cost_generator_;

		// communication cost (random) generator
		const COMMUNICATION_COST_GENERATOR communication_cost_generator_;

	public:
		
		// constructor
		RandomGenerator(){
			// nothing to do
		};

		// destructor
		virtual ~RandomGenerator(){
			// nothing to do
		};

		//************************************
		// Method:    Generate
		// FullName:  dag::RandomGenerator<TASK_COMPUTATION_COST_GENERATOR, COMMUNICATION_COST_GENERATOR>::Generate
		// Access:    public 
		// Returns:   DirectedGraph
		// Qualifier: const
		// Parameter: int node_number - total node number including one source and one sink
		//************************************
		DirectedGraph Generate( int node_number ) const {
			DirectedGraph g(node_number);

			// generate task computation cost
			for( std::pair<iter_t, iter_t> p = vertices(g); p.first != p.second; ++p.first ){
				g[ *p.first ].cost = task_computation_cost_generator_.generate();
			}

			// generate edges and communication cost
			for ( int i=0; i<node_number; i++ )
			{
				for ( int j=i+1; j<node_number; j++ )
				{
					if ( rand() % 2 )
					{
						add_edge(i,j,communication_cost_generator_.generate(),g);
					}
				}
			}

			// connect no in_edge node to source(0)
			for ( int i=1; i<node_number-1; i++ )
			{
				if( in_degree(i, g) == 0 ){
					add_edge(0,i,communication_cost_generator_.generate(),g);
				}

			}

			// connect no out_edge to sink(node_number-1)
			for ( int i=1; i<node_number-1; i++ )
			{
				if( out_degree(i, g) == 0 ){
					add_edge(i,node_number-1,communication_cost_generator_.generate(),g);
				}

			}
			

			return g;
		};

		// for debug - print out all edges
		void printGraph( const DirectedGraph& g ) const
		{
			cout << "---------- begin print graph ----------" << endl;

			graph_traits<DirectedGraph>::vertex_descriptor u, v;
			graph_traits<DirectedGraph>::edge_descriptor e;

			std::pair<edge_iterator,edge_iterator> p = edges(g);
			for(; p.first != p.second; ++p.first ){
				e = *p.first;
				u = source(e, g);
				v = target(e, g);

				cout << u << "(" <<g[u].cost << ") --(" << get(edge_weight, g, e)
					<< ")-->" << v << "(" <<g[v].cost << ")" << endl;
			}

			cout << "---------- end print graph ----------" << endl;
		};
	};
};


#endif  // FOO_BAR_BAZ_H_